package cm.twoDimensional;

public class MinPathSum {
    /**
     * https://leetcode-cn.com/problems/minimum-path-sum/submissions/
     * 状态转移方程：dp[i][j] = grid[i][j] + min(dp[i-1][j],dp[i][j-1])
     */

    public int minPathSum(int[][] grid) {
        int[] dp = new int[grid[0].length+1];

        for (int j = 1; j <= grid[0].length; j++){
            dp[j] = dp[j-1] + grid[0][j-1];
        }

        // 最左边一列之前不可达
        dp[0] = Integer.MAX_VALUE;
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j <= grid[0].length; j++) {
                dp[j] = grid[i][j-1] + Math.min(dp[j-1],dp[j]);
            }
        }
        return dp[grid[0].length];
    }

    public static void main(String[] args) {
//        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        int[][] grid = {{1,2},{1,1}};
        MinPathSum obj = new MinPathSum();
        int result = obj.minPathSum(grid);
        System.out.println(result);
    }
}
